package demo.ybt;

public class P1261 {
    public static void main(String[] args) {
        P1261 p1261= new P1261();
        int res = p1261.res(new int[][]{
                {0, 2, 5, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 12, 14, 0, 0, 0, 0},
                {0, 0, 0, 0, 6, 10, 4, 0, 0, 0},
                {0, 0, 0, 0, 13, 12, 11, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 3, 9, 0},
                {0, 0, 0, 0, 0, 0, 0, 6, 5, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 10, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 5},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        });
        System.out.println(res);
    }
    public int res(int[][] t) {
        int h = t.length;
        //宽和高是一样的
        int w = h;

        int[] dp = new int[t.length];
        //起始位置路劲为0，没有到起点的路径。（起点之前是没有路径的）
        dp[0] = 0;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                //t[i][j]=(0->1) 转移   dp[i]= dp[i] + t[i][j]
                if(t[i][j]>0){
                    int tmp = dp[i] + t[i][j];
                    if (dp[j] == 0) {
                        dp[j] = tmp;
                    } else {
                        dp[j] = Math.min(tmp, dp[j]);
                    }
                }
            }
        }
        return dp[h - 1];
    }
}
